package middle;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import middle.Solution_146.LRUCache_1.Node;

public class Solution_146 {
    static class LRUCache {
        private int limit;
        private int count;
        private Map<Integer, Node> map;
        private Node emptyHeader, emptyTail;
        public LRUCache(int capacity) {
            this.limit = capacity;
            map = new HashMap<>(capacity);
            emptyHeader = new Node(-1, -1);
            emptyTail = new Node(-1, -1);
            emptyHeader.next = emptyTail;
            emptyTail.pre = emptyHeader;
        }

        public int get(int key) {
            Node node = map.get(key);
            if (node == null) {
                return -1;
            }
            split(node);
            addToHeader(node);
            return node.val;
        }

        public void put(int key, int value) {
            Node node = map.get(key);
            if (node == null) {
                count++;
                node = new Node(key, value);
                addToHeader(node);
                map.put(key, node);
            } else {
                node.val = value;
                split(node);
                addToHeader(node);
            }
            if (count > limit && emptyTail.pre.pre != null) {
                map.remove(emptyTail.pre.key);
                emptyTail.pre.pre.next = emptyTail;
                emptyTail.pre = emptyTail.pre.pre;
                count--;
            }
        }

        private void split(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.pre = null;
            node.next = null;
        }

        private void addToHeader(Node node) {
            emptyHeader.next.pre = node;
            node.next = emptyHeader.next;
            node.pre = emptyHeader;
            emptyHeader.next = node;
        }

        static class Node {
            public int key;
            public int val;
            public Node pre;
            public Node next;
            public Node(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }
    }

    static class LRUCache_1 {

        private final Node[] array;
        private Node head;
        private int count;
        private final int limit;

        public LRUCache_1(int capacity) {
            limit = capacity;
            array = new Node[100001];
        }

        public int get(int key) {
            Node node = array[key];
            if (node != null) {
                moveToHeader(node);
                return node.value;
            }
            return -1;
        }

        public void put(int key, int value) {
            Node node = array[key];
            if (node != null) {
                // 更新以及存在的节点
                node.value = value;
                moveToHeader(node);
            } else if (limit > 0) {
                // 节点不存在，需要新增
                if (count < limit) {
                    count++;
                    node = new Node(key, value);
                    addHeader(node);
                } else {
                    // 队列已满，需要移除节点
                    node = head.pre;
                    array[node.key] = null;

                    node.key = key;
                    node.value = value;
                    head = node;
                    array[node.key] = node;
                }
                array[node.key] = node;
            }
        }

        // 将节点移动到头位置
        private void moveToHeader(Node node) {
            if (head != node) {
                split(node);
                addHeader(node);
            }
        }

        // 剥离当前节点
        private void split(Node node) {
            Node pre = node.pre;
            Node next = node.next;
            if (pre != null) {
                pre.next = next;
            }
            if (next != null) {
                next.pre = pre;
            }
        }

        // 将节点添加到头位置
        private void addHeader(Node node) {
            if (head == null) {
                node.next = node;
                node.pre = node;
                head = node;
            } else {
                Node last = head.pre;
                node.pre = last;
                node.next = head;
                head.pre = node;
                last.next = node;
                this.head = node;
            }
        }

        static class Node {

            public Node pre;
            public Node next;
            public Integer key;
            public Integer value;

            public Node(Integer key, Integer value) {
                this.key = key;
                this.value = value;
            }
        }

        //        private int size;
        //        private Map<Integer, Item> map;
        //        private PriorityQueue<Item> queue;
        //        private long seq;
        //
        //        public LRUCache(int capacity) {
        //            size = capacity;
        //            map = new HashMap<>(size);
        //            queue = new PriorityQueue<>((e1, e2) -> (int) (e1.time - e2.time));
        //        }
        //
        //        public int get(int key) {
        //            if (map.containsKey(key)) {
        //                // 更新key的时间戳
        //                Item item = map.get(key);
        //                item.time = ++seq;
        //                queue.remove(item);
        //                queue.add(item);
        //                return item.value;
        //            }
        //            return -1;
        //        }
        //
        //        public void put(int key, int value) {
        //            if (map.containsKey(key)) {
        //                Item item = map.get(key);
        //                item.value = value;
        //                item.time = ++seq;
        //                queue.remove(item);
        //                queue.add(item);
        //            } else {
        //                if (map.size() >= size && !queue.isEmpty()) {
        //                    Item poll = queue.poll();
        //                    map.remove(poll.key);
        //                }
        //                if (map.size() < size) {
        //                    Item item = new Item();
        //                    item.key = key;
        //                    item.value = value;
        //                    item.time = ++seq;
        //                    queue.add(item);
        //                    map.put(key, item);
        //                }
        //            }
        //        }
        //
        //        static class Item {
        //
        //            public Integer key;
        //            public Integer value;
        //            public Long time;
        //        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
//        cache.put(2, 1);
//        cache.put(1, 1);
//        System.out.println(cache.get(2));
//        cache.put(4, 1);
//        System.out.println(cache.get(1));
//        System.out.println(cache.get(2));

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));

//        System.out.println(cache.get(2));
//        cache.put(2, 6);
//        System.out.println(cache.get(1));
//        cache.put(1, 5);
//        cache.put(1, 2);
//        System.out.println(cache.get(1));
//        System.out.println(cache.get(2));

//                cache.put(2, 1);
//                cache.put(1, 1);
//                cache.put(2, 3);
//                cache.put(4, 1);
//                System.out.println(cache.get(1));
//                System.out.println(cache.get(2));

//        cache.put(10, 13);
//        cache.put(3, 17);
//        cache.put(6, 11);
//        cache.put(10, 5);
//        cache.put(9, 10);
//        System.out.println(cache.get(13));
//        cache.put(2, 19);
//        System.out.println(cache.get(2));
//        System.out.println(cache.get(3));
//        cache.put(5, 25);
//        System.out.println(cache.get(8));
//        cache.put(9, 22);
//        cache.put(5, 5);
//        cache.put(1, 30);
//        System.out.println(cache.get(11));
//        cache.put(9, 12);
//        System.out.println(cache.get(7));
//        System.out.println(cache.get(5));
//        System.out.println(cache.get(8));
//        System.out.println(cache.get(9));
//        cache.put(4, 30);
//        cache.put(9, 3);
//        System.out.println(cache.get(9));
//        System.out.println(cache.get(10));
//        System.out.println(cache.get(10));
//        cache.put(6, 14);
//        cache.put(3, 1);
//        System.out.println(cache.get(3));
//        cache.put(10, 11);
//        System.out.println(cache.get(8));
//        cache.put(2, 14);
//        System.out.println(cache.get(1));
//        System.out.println(cache.get(5));
//        System.out.println(cache.get(4));
//        cache.put(11, 4);
//        cache.put(12, 24);
//        cache.put(5, 18);
//        System.out.println(cache.get(13));
//        cache.put(7, 23);
//        System.out.println(cache.get(8));
//        System.out.println(cache.get(12));
//        cache.put(3, 27);
//        cache.put(2, 12);
//        System.out.println(cache.get(5));
//        cache.put(2, 9);
//        cache.put(13, 4);
    }
}
